/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package routefinder.implementation;

import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import routefinder.City;
import routefinder.Link;

/**
 * An adaptation of the algorithm found on the internet for Dijkstra's shortest path algorithm.
 *
 * @see #getShortestDistance(routefinder.City)
 * @see #getShortestDistances()
 * @see #execute(City, City)
 * 
 */
public class Dijkstra {

    /**
     * Infinity value for distances.
     */
    public static final int INFINITE_DISTANCE = Integer.MAX_VALUE;
    /**
     * Some value to initialize the priority queue with.
     */
    private static final int INITIAL_CAPACITY = Configuration.getInstance().getPropertyAsInt("priorityQueue.initialCapacity");
    /**
     * The graph.
     */
    private final IRoutesMap map;
    /**
     * The working set of cities, kept ordered by shortest distance.
     * 
     * This comparator orders cities according to their shortest distances,
     * in ascending fashion. If two cities have the same shortest distance,
     * we compare the cities themselves.
     */
    private final PriorityQueue<City> unsettledNodes = new PriorityQueue<City>(INITIAL_CAPACITY, new ShortestDistanceComparator());
    /**
     * The set of cities for which the shortest distance to the source
     * has been found.
     */
    private final Set<City> settledNodes = new HashSet<City>();
    /**
     * The currently known shortest distance for all cities.
     */
    private final Map<City, Integer> shortestDistances = new HashMap<City, Integer>();

    /**
     * @param a representation of the graph
     */
    public Dijkstra(IRoutesMap map) {
        this.map = map;
    }

    /**
     * Initialize all data structures used by the algorithm.
     * 
     * @param start the source node
     */
    private void init(City start) {
        settledNodes.clear();
        unsettledNodes.clear();

        shortestDistances.clear();

        // add source
        setShortestDistance(start, 0);
        unsettledNodes.add(start);
    }

    /**
     * Run Dijkstra's shortest path algorithm on the map.
     * The results of the algorithm are available through
     * {@link #getPredecessor(City)}
     * and 
     * {@link #getShortestDistance(City)}
     * upon completion of this method.
     * 
     * @param start the starting city
     * @param destination the destination city. If this argument is <code>null</code>, the algorithm is
     * run on the entire graph, instead of being stopped as soon as the destination is reached.
     */
    protected void execute(City start, City destination) {
        init(start);

        // the current node
        City u;

        // extract the node with the shortest distance
        while ((u = unsettledNodes.poll()) != null) {
            // destination reached, stop
            if (u == destination) {
                break;
            }
            settledNodes.add(u);
            relaxNeighbors(u);
        }
    }

    /**
     * Compute new shortest distance for neighboring nodes and update if a shorter
     * distance is found.
     *
     * @param u the node
     */
    private void relaxNeighbors(City u) {
        for (Link v : map.getDestinations(u)) {
            // skip node already settled
            if (isSettled(v.getCity())) {
                continue;
            }

            int shortDist = getShortestDistance(u) + v.getDistance();

            if (shortDist < getShortestDistance(v.getCity())) {
                // assign new shortest distance and mark unsettled
                setShortestDistance(v.getCity(), shortDist);
            }
        }
    }

    /**
     * Test a node.
     *
     * @param v the node to consider
     * 
     * @return whether the node is settled, ie. its shortest distance
     * has been found.
     */
    private boolean isSettled(City v) {
        return settledNodes.contains(v);
    }

    /**
     * @return the shortest distance from the source to the given city, or
     * {@link Dijkstra#INFINITE_DISTANCE} if there is no route to the destination.
     */
    protected int getShortestDistance(City city) {
        Integer d = shortestDistances.get(city);
        return (d == null) ? INFINITE_DISTANCE : d;
    }

    /**
     * Set the new shortest distance for the given node,
     * and re-balance the queue according to new shortest distances.
     *
     * This method along with getShortestDistance represents the major
     * bottleneck of the algorithm.
     *
     * @param city the node to set
     * @param distance new shortest distance value
     */
    private void setShortestDistance(City city, int distance) {
        unsettledNodes.remove(city);

        // Update the shortest distance.
        shortestDistances.put(city, distance);

        /*
         * Re-balance the queue according to the new shortest distance found
         * (see the comparator the queue was initialized with).
         */
        unsettledNodes.add(city);
    }

    protected Map<City, Integer> getShortestDistances() {
        HashMap<City, Integer> casted = (HashMap<City, Integer>) shortestDistances;
        return (HashMap<City, Integer>) casted.clone();
    }

    private class ShortestDistanceComparator implements Comparator<City> {

        public int compare(City left, City right) {
            int result = getShortestDistance(left) - getShortestDistance(right);
            if (result == 0) {
                result = left.getName().compareTo(right.getName());
            }
            return result;
        }
    }
}
